#include <iostream>
#include <memory>

using namespace std;

static const double BALFACTOR = 0.25;
static const int MAXLEVEL = 32;

template <typename _C>
struct SLNodeLevel;

template <typename _C>
struct SLNode
{
    _C key_;
    SLNodeLevel<_C> *forwards_;
    SLNode<_C> *backward_;

    SLNode(const _C &k, int level)
        : key_(k), forwards_(new SLNodeLevel<_C>[level]) {}
    ~SLNode() { delete[] this->forwards_; }
};

template <typename _C>
struct SLNodeLevel
{
    SLNode<_C> *forward_;
    int span_;
};

template <typename _C, typename _Comp = std::less<_C>>
struct SkipList
{
    int level_;
    SLNode<_C> *head_, *tail_;
    int count_;

    SkipList() { this->createList(); }
    ~SkipList() { this->freeList(); }

    static int getRankdomLevel();
    static bool eleEqual(const _C &lhs, const _C &rhs);
    void createList();
    void freeList();
    int search(const _C &);
    void insert(const _C &);
    void remove(const _C &);
    void dumpAllNodes();
};

template <typename _C, typename _Comp>
int SkipList<_C, _Comp>::getRankdomLevel()
{
    int level = 1;
    while ((random() & 0xFFFF) < (BALFACTOR * 0xFFFF))
        ++level;
    return MAXLEVEL > level ? level : MAXLEVEL;
}

template <typename _C, typename _Comp>
bool SkipList<_C, _Comp>::eleEqual(const _C &lhs, const _C &rhs)
{
    _Comp comp;
    if (!comp(lhs, rhs) && !comp(rhs, lhs))
        return true;
    return false;
}

template <typename _C, typename _Comp>
void SkipList<_C, _Comp>::createList()
{
    this->tail_ = nullptr;
    this->head_ = new SLNode<_C>(_C(), MAXLEVEL);
    for (int i = 0; i < MAXLEVEL; ++i)
    {
        auto &forward = this->head_->forwards_[i];
        forward.forward_ = nullptr;
        forward.span_ = 0;
    }
    this->head_->backward_ = nullptr;
    this->count_ = 0;
    this->level_ = 1;
}

template <typename _C, typename _Comp>
void SkipList<_C, _Comp>::freeList()
{
    SLNode<_C> *p = this->head_, *q;
    while (p)
    {
        q = p->forwards_[0].forward_;
        delete p;
        p = q;
    }
}

template <typename _C, typename _Comp>
int SkipList<_C, _Comp>::search(const _C &k)
{
    _Comp comp;
    int rank = 0;
    auto node = this->head_;

    for (int i = this->level_ - 1; i >= 0; --i)
    {
        while (node->forwards_[i].forward_ && comp(node->forwards_[i].forward_->key_, k))
        {
            rank += node->forwards_[i].span_;
            node = node->forwards_[i].forward_;
        }
    }
    ++rank;
    node = node->forwards_[0].forward_;
    if (node && this->eleEqual(node->key_, k))
    {
        return rank;
    }
    else
    {
        return 0;
    }
}

template <typename _C, typename _Comp>
void SkipList<_C, _Comp>::insert(const _C &k)
{
    _Comp comp;
    SLNode<_C> *update[MAXLEVEL], *node = this->head_;
    int rank[MAXLEVEL];
    int level = this->level_;
    for (int i = level - 1; i >= 0; --i)
    {
        rank[i] = i == (level - 1) ? 0 : rank[i + 1];
        while (node->forwards_[i].forward_ && comp(node->forwards_[i].forward_->key_, k))
        {
            rank[i] += node->forwards_[i].span_;
            node = node->forwards_[i].forward_;
        }
        update[i] = node;
    }
    node = node->forwards_[0].forward_;
    if (node && this->eleEqual(node->key_, k))
        return;

    int nodeLevel = this->getRankdomLevel();
    if (nodeLevel > level)
    {
        for (int i = level; i < nodeLevel; ++i)
        {
            rank[i] = 0;
            update[i] = this->head_;
            this->head_->forwards_[i].span_ = this->count_;
        }
        this->level_ = nodeLevel;
    }

    auto newNode = new SLNode<_C>(k, nodeLevel);
    for (int i = 0; i < nodeLevel; ++i)
    {
        node = update[i];
        auto &newLevelNode = newNode->forwards_[i];
        auto &levelNode = node->forwards_[i];
        newLevelNode.forward_ = levelNode.forward_;
        newLevelNode.span_ = levelNode.span_ - (rank[0] - rank[i]);
        levelNode.forward_ = newNode;
        levelNode.span_ = rank[0] - rank[i] + 1;
    }
    for (int i = nodeLevel; i < level; ++i)
    {
        update[i]->forwards_[i].span_++;
    }

    newNode->backward_ = (update[0] == this->head_) ? nullptr : update[0];
    if (newNode->forwards_[0].forward_)
    {
        newNode->forwards_[0].forward_->backward_ = newNode;
    }
    else
    {
        this->tail_ = newNode;
    }
    ++this->count_;
}

template <typename _C, typename _Comp>
void SkipList<_C, _Comp>::remove(const _C &k)
{
    _Comp comp;
    SLNode<_C> *update[MAXLEVEL], *node = this->head_;
    int level = this->level_;
    for (int i = level - 1; i >= 0; --i)
    {
        while (node->forwards_[i].forward_ && comp(node->forwards_[i].forward_->key_, k))
        {
            node = node->forwards_[i].forward_;
        }
        update[i] = node;
    }
    node = node->forwards_[0].forward_;
    if (!node || !this->eleEqual(node->key_, k))
        return;
    for (int i = 0; i < level; ++i)
    {
        auto &forward = update[i]->forwards_[i];
        if (forward.forward_ != node)
        {
            --forward.span_;
        }
        else
        {
            auto &nodeForward = node->forwards_[i];
            forward.forward_ = nodeForward.forward_;
            forward.span_ += nodeForward.span_ - 1;
        }
    }
    if (node->forwards_[0].forward_)
    {
        node->forwards_[0].forward_->backward_ = node->backward_;
    }
    else
    {
        this->tail_ = node->backward_;
    }
    delete node;
    while (this->level_ > 1 && !this->head_->forwards_[this->level_ - 1].forward_)
    {
        --this->level_;
    }
    --this->count_;
}

template <typename _C, typename _Comp>
void SkipList<_C, _Comp>::dumpAllNodes()
{
    int level = this->level_;
    for (int i = level - 1; i >= 0; --i)
    {
        auto node = this->head_;

        while (node->forwards_[i].forward_)
        {
            cout << node->key_ << "(" << node->forwards_[i].span_ << ") ";
            node = node->forwards_[i].forward_;
        }
        cout << node->key_ << "(" << node->forwards_[i].span_ << ") ";
        cout << endl;
    }
}

struct Test
{
    int uid;
    int score;
};

ostream &operator<<(ostream &os, const Test &t)
{
    cout << "uid:" << t.uid << "score:" << t.score;
}

struct TestComp
{
    bool operator()(const Test &lhs, const Test &rhs)
    {
        if (lhs.score != rhs.score)
            return lhs.score > rhs.score;
        return lhs.uid < rhs.uid;
    }
};

// valgrind --tool=memcheck --leak-check=yes
int main()
{
    SkipList<int> is;
    is.insert(10);
    is.dumpAllNodes();

    SkipList<Test, TestComp> p;
    for (int i = 1; i < 20; ++i)
    {
        p.insert({20 - i, i});
    }
    cout << p.search({10, 10}) << endl;
    p.remove({10, 10});
    p.dumpAllNodes();
}